package 力扣算法练习.main1.part1;

import java.util.List;

public class day10 {
    /*
    整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
    例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
    整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，
    如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的
    下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一
    个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
    https://leetcode.cn/problems/next-permutation
     */
    //错误代码
    /*public static void nextPermutation(int[] nums) {
        if (nums.length < 2) return;
        //先找有没有下一个排列,没有就将数组反转
        int temp;//记录交换的数值
        boolean flag = true;//记录有没有下一个排列
        //有下一个排列
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    temp=nums[i];
                    //将j位置和后面的元素向后移
                    for (int k=i; k>j ; k--) {
                        nums[k]=nums[k-1];
                    }
                    nums[j]=temp;
                    flag=false;
                    break;
                }
            }
            if (!flag)break;//找到了下一个队列退出外层循环
        }
        //如果flag还是为TRUE说明没有下一个排列,将其反转
        if (flag) {
            int index = nums.length - 1;
            for (int i = 0; i < nums.length - 1; i++) {
                if (i > index) break;
                temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
                index--;
            }
        }
    }*/


    //官方解

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}
